package com.algorithm.ZeroOnePackage;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Stack;

public class Main {
    public static void main(String[] args){

        int capacity=300;

        //创建栈，用来顺序输出哪些元素被选了
        Stack<Boolean> stack=new Stack<Boolean>();

        //生成100个物品
        Goods[] goods=new Goods[10];
        for(int i=0;i<goods.length;i++){
            goods[i]=new Goods();
        }
        int[] randomNumbers=new int[100];
        generate(randomNumbers);
        for(int i=0;i<goods.length;i++){
            goods[i].price=randomNumbers[i];
        }
        generate(randomNumbers);
        for(int i=0;i<goods.length;i++){
            goods[i].weight=randomNumbers[i];
        }

        //创建优先队列
        //先创建比较器
        Comparator<Node> cmp=new Comparator<Node>() {
            @Override
            public int compare(Node goodsNode, Node t1) {
                return t1.prospect-goodsNode.prospect;  //从大到小排列
            }
        };
        //再创建优先队列实例
        PriorityQueue<Node> priorityQueue=new PriorityQueue<>(cmp);

        //创建根节点
        Node rootNode=new Node();

        //初始化根节点
        rootNode.selected=false;  //根节点不选
        rootNode.father=null;     //根节点没有父节点
        rootNode.currentPrice=0;  //当前没有价值
        rootNode.currentWeight=0; //当前没有重量
        rootNode.index=-1;        //不代表任何元素
        int sumPrice=0;
        for(int i=0;i<goods.length;i++){
            sumPrice+=goods[i].price;
        }
        rootNode.prospect=sumPrice;  //前途是所有货物价值总和

        //将根节点放入优先队列
        priorityQueue.add(rootNode);

        //用分支限界求出最优值
        int highestPrice=0;   //设置最优值初始为0
        Node resultNode=null; //创建结果节点，以该节点为头节点的链表就是最优结果。
        while (!priorityQueue.isEmpty()){
            //从优先队列中取出队首结点
            Node fatherNode=priorityQueue.poll();
            //如果队首节点没有前途，剪枝
            if(fatherNode.prospect < highestPrice){
                continue;
            }
            //如果父节点就是最后一个元素，则直接进入下一重循环
            if(fatherNode.index==goods.length-1){
                continue;
            }
            //对队首节点进行扩展
            //创建左孩子节点
            Node leftChildNode=new Node();
            leftChildNode.index=fatherNode.index+1;//进入父节点的下一层节点
            leftChildNode.selected=true;           //该节点入选
            leftChildNode.currentPrice=fatherNode.currentPrice+goods[leftChildNode.index].price;  //当前的价值=父节点的价值+对应货物的价值
            leftChildNode.currentWeight=fatherNode.currentWeight+goods[leftChildNode.index].weight; //当前的重量=父节点的重量+对应货物的重量
            leftChildNode.father=fatherNode;       //设置该节点的父节点
            leftChildNode.prospect=fatherNode.prospect; //该节点的前途=父节点的前途
            //创建右孩子节点
            Node rightChildNode=new Node();
            rightChildNode.index=fatherNode.index+1;//进入父节点的下一层节点
            rightChildNode.selected=false;          //该节点不选
            rightChildNode.currentPrice=fatherNode.currentPrice;  //当前的价值=父节点的价值
            rightChildNode.currentWeight=fatherNode.currentWeight;//当前的重量=父节点的重量
            rightChildNode.father=fatherNode;       //设置该节点的父节点
            rightChildNode.prospect=fatherNode.prospect-goods[leftChildNode.index].price;  //该节点前途=父节点前途-对应货物的价值
            //将孩子节点入队,同时更新最优值
            //判断左孩子是否超重
            if(leftChildNode.currentWeight < capacity){
                priorityQueue.add(leftChildNode); //如果没超重，左孩子入队
                //更新最优值
                if(leftChildNode.currentPrice>highestPrice){
                    highestPrice=leftChildNode.currentPrice;
                    resultNode=leftChildNode;
                }
            }
            //判断右孩子是否入队（是否剪枝）
            if(rightChildNode.prospect>highestPrice){
                priorityQueue.add(rightChildNode);
            }
        }

        for(int i=0;i<goods.length;i++){
            System.out.println("price="+goods[i].price+" weight="+goods[i].weight);
        }
        //将哪些物品选中了打印出来
        for(Node node=resultNode;node.index!=-1;node=node.father){
            stack.push(node.selected);
        }
        while (!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
        for(int i=resultNode.index;i<goods.length-1;i++){
            System.out.print("false ");
        }
        System.out.println(highestPrice);
        System.out.println("sumPrice="+sumPrice);
        System.out.println("highestPrice="+highestPrice);

    }

    //生成随机数
    private static void generate(int[] test) {
        // 产生数据
        Random r = new Random();
        for(int i=0; i<test.length; i++){
            test[i] = r.nextInt(100);
        }
    }
}
